Integer Divides Sum of Coprime Numbers Less Than It

Proof

Consider the sum on the right reduced modulo $n$, noting that of course $gcd(n,k)=gcd(n,n-k)$. This means that for each $k$ which appears on the right hand side, so does $n-k$ given also that

When adding these pairs, we have $k+n-k=n\equiv 0(\mathrm{mod}n)$. As such, we can pair all elements in the sum such that each pair adds to zero.

The only way in which this may fail is if $k=n-k$, however this implies $n=2k$ and since $gcd(k,n)=1$, this means that $k=1$ and $n=2$, a case which we disregarded in the assumption of the theorem, and for which the result does not hold.